/*
 * @lc app=leetcode.cn id=449 lang=cpp
 *
 * [449] 序列化和反序列化二叉搜索树
 *
 * https://leetcode.cn/problems/serialize-and-deserialize-bst/description/
 *
 * algorithms
 * Medium (56.63%)
 * Likes:    340
 * Dislikes: 0
 * Total Accepted:    35.5K
 * Total Submissions: 59.4K
 * Testcase Example:  '[2,1,3]'
 *
 * 序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。
 * 
 * 设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。
 * 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。
 * 
 * 编码的字符串应尽可能紧凑。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：root = [2,1,3]
 * 输出：[2,1,3]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：root = []
 * 输出：[]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 树中节点数范围是 [0, 10^4]
 * 0 <= Node.val <= 10^4
 * 题目数据 保证 输入的树是一棵二叉搜索树。
 * 
 * 
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(root == NULL) return "";
        vector<int> path;
        preorder(root, path);
        string res;
        for(int num : path) {
            // cout<<num<<" ";
            res.append(to_string(num) + ",");
        }
        // cout<<endl;
        res.pop_back();

        // for(char c : res) cout<<c;
        // cout<<endl;

        return res;
    } 

    void preorder(TreeNode* root, vector<int>& path) {
        if(root == NULL) return;
        path.push_back(root->val);
        if(root->left) preorder(root->left, path);
        if(root->right) preorder(root->right, path);
    }

    // Decodes your encoded data to tree.
    vector<int> stringToInt(string data) {
        vector<int> res;
        string temp ="";
        data += ",";
        for(auto c : data) {
            if(c == ',') {
                // cout<<stoi(temp)<<"*";
                res.push_back(stoi(temp));
                temp = "";
            } else {
                temp += c;
            }
        }
        // cout<<endl;
        return res;
    }
    TreeNode* construct(const vector<int> preorder, int preorderBegin, int preorderEnd, const vector<int> inorder, int inorderBegin, int inorderEnd) {
       if(preorderBegin == preorderEnd) return NULL;
        int rootVal = preorder[preorderBegin];
        TreeNode* root = new TreeNode(rootVal);
        if(preorderEnd - preorderBegin == 1) return root;

        int rootValInorderIndex = 0;
        for(int i = 0; i < inorder.size(); i++) {
            if(inorder[i] == rootVal) {
                rootValInorderIndex = i;
                break;
            } 
        }

        //划分中序序列
        int inorderLeftBegin = inorderBegin;
        int inorderLeftEnd = rootValInorderIndex;
        // cout<<"中序左： ";
        // for(int i = inorderLeftBegin; i < inorderLeftEnd; i++) {
        //     cout<<inorder[i]<<" ";
        // }
        // cout<<endl;

        int inorderRightBegin = rootValInorderIndex + 1;
        int inorderRightEnd = inorderEnd;
        // cout<<"中序右： ";
        // for(int i = inorderRightBegin; i < inorderRightEnd; i++) {
        //     cout<<inorder[i]<<" ";
        // }
        // cout<<endl;
        //划分后序序列

        int preorderLeftBegin = preorderBegin + 1;
        int preorderLeftEnd = preorderLeftBegin + inorderLeftEnd - inorderLeftBegin;
        // cout<<"前序左： ";
        // for(int i = preorderLeftBegin; i < preorderLeftEnd; i++) {
        //     cout<<preorder[i]<<" ";
        // }  
        // cout<<endl;     
        int preorderRightBegin = preorderLeftEnd;
        int preorderRightEnd = preorderEnd;
        // cout<<"前序右： ";
        // for(int i = preorderRightBegin; i < preorderRightEnd; i++) {
        //     cout<<preorder[i]<<" ";
        // }  
        // cout<<endl;

        root->left = construct(preorder, preorderLeftBegin, preorderLeftEnd, inorder, inorderLeftBegin, inorderLeftEnd);
        root->right = construct(preorder, preorderRightBegin, preorderRightEnd, inorder, inorderRightBegin, inorderRightEnd);
    
        return root;
    }
    TreeNode* deserialize(string data) {
        if(data.empty()) return NULL;
        vector<int> preorder;
        preorder = stringToInt(data);
        vector<int> inorder(preorder);
        sort(inorder.begin(), inorder.end());
        // cout<<"中序遍历： ";
        // for(int i : inorder) cout<<i<<" ";
        // cout<<"前序遍历： ";
        // for(int i : preorder) cout<<i<<" ";
        TreeNode* root = construct(preorder, 0, preorder.size(), inorder, 0, inorder.size());
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec* ser = new Codec();
// Codec* deser = new Codec();
// string tree = ser->serialize(root);
// TreeNode* ans = deser->deserialize(tree);
// return ans;
// @lc code=end

